\section{Appendix}

\subsection{Optimizing the search for R4}
It is possible to optimize the known plaintext attack by filtering for the
correct $R4$ value. We use the fact that the system of linear equations are
overdetermined.
We can compute a matrix $V_{R4}$, representing the system of equations. We have the following relation between $V_{R4}$ and $(k_1 \oplus
k_2)$:

\be{matrixkey}
V_{R4} \cdot v = k_1 \oplus k_2 \ee

where $v$ is a vector containing all the variables from the linear equations.

To solve a system of equations, we use Gauss elimination. Using Gauss
elimination we start out by putting the matrix $V_{R4}$ on row echelon form.
Since the equation system is overdetermined, the last $n$ rows will be zero rows
in the matrix. We denote the permutated matrix $V'_{R4}$. It is possible to express
the row operations required to put $V_{R4}$ on row echelon form, as a matrix $T_{R4}$:

\be{rowechelon}
T_{R4} \cdot V_{R4} = V'_{R4} \ee

Multiplying \rf{matrixkey} with $T_{R4}$ will thus yield:

\be{matrixkey}
T_{R4} \cdot V_{R4} \cdot v = V'_{R4} \cdot v =  T_{R4} \cdot (k_1 \oplus k_2)
\ee

The result of multiplying $k_1 \oplus k_2$ with $T_{R4}$ is a
bit-vector where the last $n$ bits is zero (corresponding to the $n$ zero rows
in $V_{R4}$).
Thus we can denote the matrix consisting of the $n$ last rows
of $T_{R4}$ as $T^0_{R4}$, and get the following:

\be{eqzerovector}
T^0_{R4} \cdot (k_1 \oplus k_2) = {\bf 0} \ee

where {\bf 0}  is the zero vector.


Now, the way this optimization work, is that we for every possible value of $R4$
precompute $V_{R4}$ and from that $T^0_{R4}$. We can then disqualify a possible
value by taking the dot product between $R4$ and the rows of $T^0_{R4}$, and
check that it does indeed equals {\bf 0}.
If it doesn't we can disqualify that particular $R4$ value.

It takes two dot products on average to disqualify a wrong $R4$ \cite{bbk}. So
since we averagely find the correct $R4$ after $\frac{2^{16}}{2}$ tries, we will
need to calculate approximately $2^{16}$ dot products to find the correct $R4$.
Comparing that to solving $\frac{2^{16}}{2}$ systems of linear equation, the
speed improvement is obvious.
 

